The Byzantine general, Nikiforos Fokas, liberated Crete from Arab rule in 961 A.D. Iraklion fell into Byzantine hands after a four month siege, with Arab losses estimated at 200,000. Fokas built the Byzantine castle of Temenos (Kanli Kastelli) and attempted to move the city of Iraklion there. This did not materialize and the city remained where it was. Christianity flourished again and Iraklion became the seat of an archbishop. Churches and monasteries sprang up all over the island. Some of the more important churches are: the Panagia Kera Church in Kritsa; the Rotunda of Michael Archangelos, Episkopi; Ai Yannis Kyr-Yannis Church, Alikianos; Agios Nikolaos Church, Kyriakoselia; Agios Fanourios Church of the Moni Varsamonerou; Agios Pandeleimonos Church, Pigi; and Agios Fanourios Church, Kitharida. Some of the important monasteries of the period are: Moni Arkadiou, Moni Palianis, Moni Gouverniotissa, Moni Agias Triadas, Moni Gouvernetou, Moni Vrondisi, Moni Agarathou, Moni Toplou, Moni Halepa, and Moni Preveli.

Also, during this time, Byzantine noble families and many of General Fokas' troops settled on the island and built new villages.